package 左哥算法.ch16小结构;

import java.util.Stack;

/**
 * 设计一个栈，要求栈的pop，push，以及获取栈中最小值的操作均为 O(1)
 */
public class O1复杂度的栈 {

    public static void main(String[] args) {
        Structure stack=new Structure();
        stack.push(3);
        stack.push(4);
        stack.push(2);
        stack.push(6);

        System.out.println(stack.getMin());
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());
    }
    /**
     * 思路，准备两个栈。
     *  一个存储元素，一个存储栈中元素个数为k时，栈中的最小值
     *  当压栈时，查看元素是否比min栈顶元素要小，小则压入。大则再压入栈顶元素。
     */
    static class Structure{
        private Stack<Integer> stack=new Stack<>();
        private Stack<Integer> minStack=new Stack<>();
        public void push(Integer node){
            stack.push(node);
            Integer peek=minStack.isEmpty()?Integer.MAX_VALUE:minStack.peek();
            minStack.push(Math.min(node,peek));  //如果新压入的比当前要大，则重复压入栈顶元素。
        }
        public Integer pop(){
            minStack.pop();
            return stack.pop();
        }
        public Integer getMin(){
            return minStack.peek();
        }
    }
}
